package com.dateConstruction._02_singlyLinkedList;

public class PrimeList {
    
    // 素数范围上限
    private int range;
    // 单链表，存储素数线性表
    private SinglyLinkedList<Integer> list;
    
    // 构造方法，存储2-range中所有素数
    public PrimeList(int range) {
        if (range < 1) {
            throw new IllegalArgumentException("range = " + range);
        }
        this.range = range;
        this.list = new SinglyLinkedList<Integer>();
        // 先添加2
        list.insert(0, 2);
        // 尾指针rear
        Node<Integer> rear = this.list.head.next;
        // 只需对奇数判断
        for (int key = 3; key <= range; key += 2) {
            if (isPrime(key)) {
                rear.next = new Node<Integer>(key, null);
                rear = rear.next;
            }
        }
    }
    
    public boolean isPrime(int key) {
        // TODO Auto-generated method stub
        int sqrt = (int) Math.sqrt(key);
        for (Node<Integer> p = this.list.head.next; p != null && p.data <= sqrt; p = p.next) {
            if (key % p.data == 0) {
                return false;
            }
        }
        return true;
    }
    
    public String toString() {
        return "2~" + range + "素数集合：" + list.toString() + ", " + list.size() + "个元素";
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        PrimeList pl = new PrimeList(20);
        System.out.println(pl);
    }

}
